1760E - Binary Inversions - CodeForces Solution

#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
#include "bits/stdc++.h"
using namespace std;
#define fastio ios_base::sync_with_stdio(0);cin.tie(0) 
#define pb push_back
#define mp make_pair
#define forstl(i,v) for(auto &i: v)
#define setbits(x)      __builtin_popcountll(x)
#define zrobits(x)      __builtin_ctzll(x)
#define mod             1000000007
#define inf             1e18
#define ps(x,y)         fixed<<setprecision(y)<<x
#define yes cout<<"YES"<<endl
#define no cout<<"NO"<<endl
#define print(x) cout<<x<<endl
#define imp(x) cout<<"Case #"<<x<<": IMPOSSIBLE"<<endl
#define kick_out(x, r) cout<<"Case #"<<x<<": "<<r<<endl
#define testcase(t) int t;cin>>t;while(t--)
#pragma GCC diagnostic ignored "-Wc++11-extensions"
#pragma GCC diagnostic ignored "-Wc++14-extensions"

typedef long long ll; typedef unsigned long long ull; typedef long double ld; typedef pair<ll, ll> p64; typedef vector<ll> vll; typedef vector<vll> vvll; typedef vector<p64> vp64; typedef map<int, int> m32; typedef map<ll, ll> mll;

const ll LIM = 2e5 + 5, MOD = 1e9 + 7, pMOD = 998244353;
const ld EPS = 1e-9;
void bandev() {
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif
}
ll modInverse(ll a, ll m){ll m0 = m, y = 0, x = 1;if (m == 1){ return 0;}while(a > 1){ ll q = a / m; ll t = m; m = a % m, a = t; t = y; y = x - q * y; x = t; }if (x < 0){ x += m0;}return x;}
ll gcd(ll a, ll b) {if(a==-1){ return b;} if(b==-1) {return a;}if (b == 0) {return a;} return gcd(b, a % b);}
void printBlArr(vector<bool> vec){for(ll i=0; i<vec.size(); i++){cout<<vec[i]<<" ";}cout<<endl;}
void printArr(vll nw){ for (ll i = 0; i < nw.size(); i++){cout << nw[i] << " ";} cout << endl; }
void printMat(vvll mat) {for (ll i = 0 ; i < mat.size() ; i++) {for (ll j = 0; j < mat[i].size() ; j++) {printf("%d ", int(mat[i][j]));}printf("\n");} }
ll sizeDecimal(ll k) {if (k == 0) {return 1;} ll num = 0;while (k > 0) {num++;k /= 10;}return num;}
bool ispal(string& str){for(ll i=0; 2*i<=str.size(); i++){if(str[i]!=str[str.size()-1-i]){return false;}}return true;}
ll sz(vll& vec){if(vec.empty()) {return 0;}return vec.size();}
ll powsGo(ll n, ll x){if(x==0) {return 1;}ll num = powsGo(n, x/2); if(x%2==1){ return (n*(num*num)%pMOD)%pMOD; } return (num*num)%pMOD;}
vll getArray(ll n){vll nw(n, 0);for(ll i=0; i<n; i++){cin>>nw[i];}return nw;}

bool debug;

bool sortNamesFir(const p64 a, const p64 b){
    if(b.first!=a.first) return b.first>a.first;
    return b.second>a.second;
}

void run_case() {
    // ll a, b, c; cin>>a>>b>>c;
    ll n ; 
    cin>>n;
    // ll m; cin>>m;
    ll cur = 0, one = 0;
    vll nw = getArray(n);
    for(ll i=0; i<n; i++){
        one += nw[i];
    }
    ll mx = 0, ans = 0;
    for(ll i=0; i<n; i++){
        if(nw[i]==0){
            ans += cur;
            ll dif = n-i-1-one;
            mx = max(dif, mx);
        }else{
            ll dif = - n + i + one;
            mx = max(dif, mx);
        }
        cur += nw[i];
    }
    print(ans + mx);
    // printArr(mw);
}

int main(){
    debug = true;
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    // bandev();

    ll t;
    cin>>t;
    while(t--){
        run_case();
    }
}